package com.lei.stack;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/**
 * LeetCode 1047. 删除字符串中的所有相邻重复项
 * 采用栈结构
 */
public class RemoveDuplicates {
    public String removeDuplicates(String s) {
        Deque<Character> q = new ArrayDeque<>();
        char ch;
        for (int i = 0; i < s.length(); i++) {
            ch = s.charAt(i);
            if(q.isEmpty() || ch != q.peek()){
                q.push(ch);
            }else {
                q.pop();
            }
        }
        Deque<Integer> stack = new LinkedList<>();
        String str ="";
        while (!q.isEmpty()){
            //注意拼接的顺序，如果是这样 str += q.pop(),生成的结果会顺序颠倒
            str =  q.pop()+str;
        }
        return str;
    }

    public static void main(String[] args) {
        String s = "abbdcv";
        RemoveDuplicates r = new RemoveDuplicates();
        System.out.println(r.removeDuplicates(s).toString());
    }
}
